1. Field
The invention is directed towards a method and apparatus for cache efficient rasterization of graphics data.
2. Background
To prepare a graphic for display or printing, graphics data is rasterized to convert the graphics data into an array of pixels (bitmap) that is then used to display or print the graphics. FIG. 1 shows a conceptual diagram of an environment 100 in which rasterization is performed. The environment 100 includes a micro-processing unit (MPU) 105, a storage device 110, a cache 115, a frame buffer 120, and an output device 125.
The MPU 105 may comprise a central processing unit (CPU) of a host computer (e.g., desktop or laptop computer, server, gaming console, cellular telephone, etc.) or be part of a graphics device (e.g., graphics accelerator) dedicated specifically for graphics production or a digital signal processing (DSP) unit tailored to performing digital signal processing algorithms. The storage device 110 may comprise various forms of memory resources, such as a permanent storage device, a mass-storage device, a removable storage device, a volatile read-and-write memory, such as a random access memory (RAM), etc.
The MPU 105 loads and executes program instructions of an application 130 to produce streams of graphics data 132. Program instructions of the graphics application 130 and generated graphics data 132 are stored to and read from the storage device 110. The generated graphics data describes a graphic (text or images) to be displayed and can be in various forms, such as equations, coordinates of vectors, vector drawings, etc. Graphics data may include any of several types of data describing a graphic, such as color, texture, depth (z) data.
After the graphics data 132 is generated, the MPU 105 prepares the graphics data for display by rasterizing the graphics data to produce a bitmap 135. During the rasterization process, the MPU 105 loads and analyzes the graphics data to produce the bitmap 135. For example, the MPU 105 may analyze depth (z) data to determine which elements of the graphic are visible and which elements of a graphic are occluded (blocked from view by other elements of the graphic). The MPU 105 may also analyze color and texture data to determine the color and texture components of the graphic. Such analysis determinations by the MPU 105 are reflected in the generated bitmap 135.
The generated bitmap 135 is stored in the frame buffer 120 and is used to display or print an image on the output device 125 (e.g., a display monitor or printer). The frame buffer 120 is typically an area of memory in a memory resource (such as the storage device 110) used to store a bitmapped graphic while the graphic is being displayed or printed on the output device 125.
During the rasterization process discussed above, the MPU 105 transfers graphics data to be rasterized from the storage device 110 to the cache 115 which the MPU 105 can typically access in a significantly shorter time than it can access the storage device 110. The MPU 105 then loads the graphics data from the cache 115 and rasterizes the graphics data to produce the bitmap 135. If the MPU later requires particular graphics data during the rasterization process, the MPU first determines if the particular graphics data is stored in the cache 115 since the access time to the cache 115 is shorter than to the storage device 110. A “cache hit” occurs if the particular graphics data exists in the cache, whereby the particular graphics data is then retrieved from the cache. A “cache miss” occurs if the particular graphics data does not exist in the cache, whereby the particular graphics data must then be transferred from the storage device 110 to the cache 115 which consumes more time and energy as compared to direct retrieval from the cache 115. As such, it is advantageous for graphics data to be retrieved directly from the cache 115 during the rasterization process as much as possible since this reduces the amount of time and energy needed. This is especially true when rasterization is being performed in a portable device (such as a laptop computer, cellular telephone, etc.) where battery power is at a premium.
Typically, however, the rasterization process is performed in an inefficient manner where a large number of graphics data transfers from the storage device to the cache are needed. This is due to this fact that conventional methods of rasterization do not maximize the transfer of graphics data to the cache where most or all of the graphics data transferred to the cache is rasterized before further graphics data is needed from the storage device. Typically then, a significant portion of the graphics data that has been loaded to the cache is not processed and discarded and then replaced by other graphics data that has been loaded from the storage device.
As such, there is a need for techniques to rasterize graphics data in an efficient manner where transfers of graphics data from the storage device to the cache are optimized so that a fewer number of graphics data transfers are needed. This would reduce the time and energy needed to perform the rasterization process.